import java.util.Stack;

// Time complexity is O(n^2)
public class ch3_6_sorted_stack{
 
	public ch3_6_sorted_stack(){
		
	}
	public static Stack<Integer> sortStack(Stack<Integer> stack){
		Stack<Integer> sortedStack = new Stack<Integer>();
		while(!stack.isEmpty()){
			int tmp = stack.pop();
			while(!sortedStack.isEmpty()&&sortedStack.peek() > tmp)
				stack.push(sortedStack.pop());
			sortedStack.push(tmp);	
		}
		return sortedStack;
	}
	
	public static void main(String[] args){
		Stack<Integer> s = new Stack<Integer>();
		s.push(4);
		s.push(2);
		s.push(5);
		s.push(8);
		s.push(1);
		s.push(0);

		Stack<Integer> r = sortStack(s);

		for (int i=r.size()-1; i>=0; i--)
			System.out.println("--"+i+"--"+r.pop());
	}
}